package datastructure.graph.有向图;

import java.util.Stack;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 5:08 下午
 */
public class DirectedCircle {
    private boolean[] marked;

    private int[] edgeTo;

    private Stack<Integer>cycle;

    private boolean[] onStack;

    private boolean hasCycle;
    public DirectedCircle(Digraph graph) {
        marked=new boolean[graph.V()];
        edgeTo=new int[graph.V()];
        onStack=new boolean[graph.V()];
        for (int v = 0; v < graph.V(); v++) {
            if (!marked[v]){
                dfs(graph,v);
            }
        }
    }





        public boolean hasCycle(){
        return hasCycle;
    }

    private void dfs(Digraph graph, int v) {
        marked[v]=true;
        onStack[v]=true;
        for (Integer w : graph.adj(v)) {
            if (hasCycle()){
                return;
            }
            if (!marked[w]){
                edgeTo[w]=v;
                dfs(graph,w);
            }else if (onStack[w]){
                hasCycle=true;
                cycle=new Stack<>();
                for (int i = v; i !=w ; i=edgeTo[i]) {
                    cycle.push(i);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v]=false;
    }

    public static void main(String[] args) {
        Digraph digraph=new Digraph(6);
        digraph.addEdge(0,1);
        digraph.addEdge(2,5);
        digraph.addEdge(5,4);
        digraph.addEdge(4,3);
        digraph.addEdge(3,5);
        digraph.addEdge(1,2);
        //存在环3>1->2>3
        DirectedCircle cycle = new DirectedCircle(digraph);
        if (cycle.hasCycle()){
            System.out.println("存在环");
            Stack<Integer> stack = cycle.cycle;
            while (!stack.isEmpty()){
                System.out.println(stack.pop());
            }
        }
    }
}
